package 动态规划;

public class 爬楼梯_重叠子问题 {
    /**
     * 题目： 给定一个共有n阶的楼梯，你每步可以上1阶或者2阶，请问有多少种方案可以爬到楼顶？
     * https://www.hello-algo.com/chapter_dynamic_programming/intro_to_dynamic_programming/
     */

    public static void main(String[] args) {
        System.out.println(climbingStairsDP(4));
    }

    /**
     * n = 0 的时候有0种办法
     * n = 1 的时候有1种办法，只爬一次
     * n = 2 的时候有2种办法，1+1 或者直接2
     * n = 3 的时候有3种办法，1+1+1 或者 1+2 或者 2+1
     * n = 4 的时候有5种办法，1+1+1+1 或者 1+2+1 或者 2+1+1 或者 2+2 或者1+1+2
     * 那么可以得到状态转移方程 dp[i] = dp[i-1] + dp[i-2]
     */
    public static int climbingStairsDP(int n) {
        if (n <= 2) {
            return n;
        }
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}
